"""
 堆排序过程
 1.建立堆
 2.得到堆顶元素，为最大元素
 3.去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
 4.堆顶元素为第二大元素
 5.重复步骤三，直到堆变空
"""
import heapq
def sift(lyst, low, high):
    """
    lyst: 列表
    low: 最小堆根节点位置
    high：堆的最后一个元素位置
    """
    i = low
    j = 2 * i + 1  # 左子节点下标
    tmp = lyst[low] # 把堆顶存起来
    while j <= high:    # 只要j位置有数
        if j + 1 <= high and lyst[j+1] > lyst[j]: # 当右孩子比左孩子大
            j = j+1     # j指向右孩子
        if lyst[j] > tmp:
            lyst[i] = lyst[j]
            i = j       # 往下看一层
            j = 2 * i + 1
        else:   # tmp更大
            break
    lyst[i] = tmp

def heap_sort(lyst):
    n = len(lyst)
    for i in range((n-2)//2, -1, -1):
        # i表示建堆时调整的部分的父节点的下标
        sift(lyst, low=i, high=n-1)
    # 堆建立完成
    for i in range(n-1, -1, -1):
        # i指向当前堆的最后一个元素
        lyst[0], lyst[i] = lyst[i], lyst[0]
        sift(lyst, 0, i-1)

